Okay, good morning everybody.

Can you hear me on Teams?

Yes.

Yes.

It's a lot.

Very good. I hope you had a great season break.

We're going again. You recorded, I hope.

Yeah, so you can revise online as well.

Okay.

Very good.

So we are almost by the end.

I'll introduce today graphs.

And as we will see, graphs are basically everything. You can represent everything as graphs.

But for generic graphs, we also need specific algorithms. So we'll do this week graphs. We'll see how far we get. I think you can get through

most of the basic materials this week. And then next week we do something else cool, which is hashing.

This is just I see it more as an add-on because it's an option you can sprinkle over all of these sort of algorithms list data structures and so on.

Okay, so let's start. You have seen in this lecture a couple of ways to represent data.

One way is just you build some list, right? You can do whatever we want here. We can implement this as a linked list.

You can just index it. Let's say this is a linked list. You just go on every node that has an idea what's the point of the next and store data that way.

We can also store data in a tree, right? You have some arbitrary choices here. In this case, I just choose that my tree is a binary tree.

So every parent has two children. I can go. You have seen certain properties. These trees can be reared. They can degenerate to a list.

You have only one side. What's the best of three? How deep are they?

Sorry?

AVL trees. Yes, this is AVL trees is a way to guarantee that the thing is balanced kind of. But an ideal tree, how deep is it?

Do you remember how many steps is it? What's the order of steps you need to take to get to any leave?

In terms of the number of elements.

Do you remember how deep is a tree? The height. What's the height of the tree? What's the order of the height?

In terms of the number of nodes. Do you remember this? All of the recursions we did. Everything point down to tree structures at some point.

So what was the height approximately?

The highest leaf, the leaf which has the most.

Okay, let's say all of them have equal height. What approximately is this height in terms of nodes?

The order of the height of a tree. Yeah, what is it?

Log N.

Log N. Exactly. Thanks a lot. So trees, log N. This is always what you probably should remember if you see a tree somewhere, you know, okay, complexity is around log N.

If the tree is well behaved and everything, of course, if the tree is not well behaved, I can either force it to be well behaved, AVL trees, what you have seen last time and so on.

Or I just leave it and say, okay, the limit, it's all N. So it should be log N in general.

Now, all of that can be represented in a different way. I'll say generic data can be represented differently. I don't need structures like that.

I can just assume I have some data lying around and data is somehow connected.

Okay, that could be a connection between one and two, but no connection between two and three and the connection between two and four.

That's it. I don't know anything else. That's the graph. That's a graph. That's a graph.

That's a graph. Very weird graph because it's kind of one dimensional, but I can represent any data that has any relationship between its elements as a graph.

And we'll talk about a lot of material in graphs. Graphs is an entire field of study. A lot of math goes into graphs.

Today we're only talking about how to represent graphs, chain or graphs, how to characterize graphs and then a few algorithms how to how to iterate through a graph, how to search through a graph.

Yeah, that's what I just said. Let's categorize graphs a little bit first. So the first thing we should consider is what our elements are called.

In a graph, I would call the nodes in general vertices. Okay, V. This is just a set of vertices and these vertices are somehow connected and the connections are called E for edges.

There are edges in between. If I do this, I mean the number of vertices and the number of edges.

As you can see, I don't have implicit bias here. I don't say, okay, there's a specific structure. So my invariant is not like in the binary tree where I know every parent has two nodes.

So I can have a lot of different numbers here. There can be a lot of nodes, but only two edges. Or there could be very few nodes, very few vertices, but a lot of edges.

So you can represent really, really a lot of things, basically everything with these sort of graphs. Now, the vertices and the edges, they might have labels or call it payload or some something stored in them.

Some other data, but these edges might also have labels, might be something like a weight. I could represent a graph like this in any spatial arrangement in any visualization.